package org.geekbang.time.mathbasicthought.lesson9_dynamic_programming;

/**
 * 最长回文子串
 */
public class LongestPalindrome {

    public static void main(String[] args) {
        System.out.println(longestPalindrome("aaaa"));
    }

    /**
     * 状态转移方程 P(i,j) = true = P(i+1,j-1) && si == sj
     * 边界条件 len=1, P(i,j) = true; len=2时, P(i, j) = true = si==sj
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        // 初始化二维数组，记录s[i...j]是否是回文
        boolean[][] arr = new boolean[len][len];
        // 初始化，长度为1的字符串是回文
        for (int i = 0; i < len; i++) {
            arr[i][i] = true;
        }

        // 记录回文字符串的起始下标、长度
        int begin = 0;
        int maxLen = 1;

        char[] chars = s.toCharArray();
        // 长度从2开始
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                // L = j - i + 1
                int j = L + i - 1;
                // 数组越界检查
                if (j >= len) {
                    break;
                }

                if (chars[i] == chars[j]) {
                    if (L <= 3) {
                        arr[i][j] = true;
                    } else {
                        arr[i][j] = arr[i + 1][j - 1];
                    }
                } else {
                    arr[i][j] = false;
                }

                // 找到一个回文即可跳出
                if (arr[i][j] && L > maxLen) {
                    begin = i;
                    maxLen = L;
                }
            }
        }

        return s.substring(begin, begin + maxLen);
    }
}
